//94. 二叉树的中序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode*root,vector<int>& res){
        if(!root){
            return;
        }
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        inorder(root,res);
        return res;
    }
};


//104. 二叉树的最大深度
//方法：深度优先搜索
class Solution {
public:
    int maxDepth(TreeNode* root) {
       if(root==nullptr)return 0;
       return max(maxDepth(root->left),maxDepth(root->right))+1; 
    }
};


//226.翻转二叉树
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        TreeNode*left=invertTree(root->left);
        TreeNode*right=invertTree(root->right);
        root->left=right;
        root->right=left;
        return root;
        
    }
};


//101. 对称二叉树
class Solution {
public:
    bool check(TreeNode*p,TreeNode*q){
        if(!p&&!q)return true;
        if(!p||!q)return false;
        return p->val==q->val && check(p->left,q->right) &&check(p->right,q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root->left,root->right);

    }
};


// 543. 二叉树的直径
//深度优先搜索
class Solution { 
public:
    int ans;
    int depth(TreeNode*rt){
        if(rt==NULL){
            return 0;//访问到空节点了
        }
        int L=depth(rt->left);// 左儿子为根的子树的深度
        int R=depth(rt->right);// 右儿子为根的子树的深度
        ans=max(ans,L+R+1);
            return max(L,R)+1;//返回该节点为根的子树的深度
    }

    int diameterOfBinaryTree(TreeNode* root) {
        ans=1;//单节点数（root);
        depth(root);
        return ans-1;//返回直径
    }
};



//102.二叉树的层次遍历 
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ret;
        if(!root){
            return ret;
        }

        queue<TreeNode*>q;//转交容器queue处理
        q.push(root);
        while(!q.empty()){
            int currentLeveSize=q.size();
            ret.push_back(vector<int>());//在 ret 中创建一个新的空一维向量，用于存储当前层的节点值
            for(int i=1;i<=currentLeveSize;i++){
                auto node=q.front();// 获取队列的队首元素，并赋值给 node
                q.pop();
                ret.back().push_back(node->val); // 将当前节点的值添加到结果向量的最后一个子向量中
                if(node->left)q.push(node->left);
                if(node->right)q.push(node->right);//加入的元素决定q.size，至多2（左右子树都有的情况）

            }
        }
        return ret;
    }
};


//1382. 将二叉搜索树变平衡(扩展)
class Solution {
public:
    vector<int> inorderSeq;

    void getInorder(TreeNode*o){
        if(o->left){
            getInorder(o->left);
        }
        inorderSeq.push_back(o->val);
        if(o->right){
            getInorder(o->right);
        }
    }

    TreeNode*build(int l,int r){
        int mid=(l+r)>>1;
        TreeNode* o=new TreeNode(inorderSeq[mid]);//选取 inorderSeq[mid] 作为当前子树的根节点。
        if(l<=mid-1){
            o->left=build(l,mid-1);//二分思想
        }
        if(mid+1<=r){
            o->right=build(mid+1,r);
        }
        return o;
    }
    TreeNode* balanceBST(TreeNode* root) {
        getInorder(root);
        return build(0,inorderSeq.size()-1);
    }
};



//108. 将有序数组转换为二叉搜索树
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums,0,nums.size()-1);
    }

    TreeNode* helper(vector<int>& nums,int left,int right){
        if(left>right){
            return nullptr;
        }
        // 总是选择中间位置左边的数字作为根节点
        int mid=(left+right)/2;

        TreeNode*root=new TreeNode(nums[mid]);
        root->left=helper(nums,left,mid-1);
        root->right=helper(nums,mid+1,right);
        return root;
    }
};


//98. 验证二叉搜索树
class Solution {
public:
    //递归
    bool helper(TreeNode*root,long long lower,long long upper){
        if(root==nullptr){
            return true;
        }
        if(root->val<=lower||root->val>=upper){
            return false;
        }
        return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);
    }
};


// 230. 二叉搜索树中第 K 小的元素
class Solution {
public:
    int kthSmallest(TreeNode* root, int& k) {//使用引用传递 k 是为了保证在递归调用过程中，k 的值能在不同层级的函数调用之间保持同步。如果采用值传递，每次递归调用时都会创建一个新的 k 的副本，那么在递归返回时，k 的值不会被正确更新，从而无法正确找到第 k 小的元素。
        if(root==nullptr){
            return -1;//用 -1 表示没有找到
        }
        int left_res=kthSmallest(root->left,k);
        if(left_res!=-1){
            return left_res;
        }
        if(--k==0){
            return root->val;
        }
        return kthSmallest(root->right,k);// 右子树会返回答案或者 -1
    }
};



//199. 二叉树的右视图

//广度优先搜索
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int,int>rightmostValueAtDepth;
        int max_depth=-1;

        queue<TreeNode*>nodeQueue;//数组->队列->树的节点
        queue<int> depthQueue;
        nodeQueue.push(root);
        depthQueue.push(0);

        while(!nodeQueue.empty()){
            TreeNode* node=nodeQueue.front();nodeQueue.pop();
            int depth=depthQueue.front();depthQueue.pop();

            if(node!=NULL){
                max_depth=max(max_depth,depth);
 // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth[depth]=node->val;

                nodeQueue.push(node->left);
                nodeQueue.push(node->right);
                depthQueue.push(depth+1);//对应左子节点的深度
                depthQueue.push(depth+1);//对应右子节点的深度
            
            }
        }
        vector<int> rightView;
        for(int depth=0;depth<=max_depth;depth++){
            rightView.push_back(rightmostValueAtDepth[depth]);
        }
        return rightView;
    }
};


//114. 二叉树展开为链表
//114. 二叉树展开为链表
class Solution {
public:
    void DLRTree(TreeNode* root,vector<TreeNode*>&l){
        if(root!=NULL){
            l.push_back(root);
            DLRTree(root->left,l);
            DLRTree(root->right,l);

        }
    }

    void flatten(TreeNode* root) {
        vector<TreeNode*>l;
        DLRTree(root,l);
        int n=l.size();
        for(int i=1;i<n;i++){
            TreeNode*prev=l.at(i-1),*curr=l.at(i);
            prev->left=nullptr;
            prev->right=curr;
        }
    }
};



//105. 从前序与中序遍历序列构造二叉树
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        for(int i = 0; i < inorder.size(); i++)
            dic[inorder[i]] = i;
        return recur(0, 0, inorder.size() - 1);
    }
private:
    vector<int> preorder;
    unordered_map<int, int> dic;
    TreeNode* recur(int root, int left, int right) { 
        if (left > right) return nullptr;                   // 递归终止
        TreeNode* node = new TreeNode(preorder[root]);      // 建立根节点
        int i = dic[preorder[root]];          // 划分根节点、左子树、右子树
        node->left = recur(root + 1, left, i - 1);      // 开启左子树递归
        node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                          // 回溯返回根节点
    }
};


//437. 路径总和 III

class Solution {
public:
    int rootSum(TreeNode* root,long targetSum){
        if(!root){
            return 0;
        }
        int ret=0;
        if(root->val==targetSum){
            ret++;
        }

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);

        return ret;
    }
    int pathSum(TreeNode* root, int targetSum) {
         if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;


    }
};


//236. 二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       if(root==nullptr||root==p||root==q)return root;
       TreeNode *left=lowestCommonAncestor(root->left,p,q);
       TreeNode *right=lowestCommonAncestor(root->right,p,q);
       if(left==nullptr)return right;
       if(right==nullptr)return left; 
        return root;
    }
};


